#!/usr/env/bin python
# -*- coding: utf-8 -*-

# @Time    : 2020-07-25 8:59 上午
# @Author  : yangdy
# @File    : 2020-07-25.410.分割数组的最大值
# @Software: PyCharmCE
from my_methods import *


class Solution:
    def splitArray(self, nums: List[int], m: int) -> int:
        ans = 0
        n = len(nums)
        # 1. dp
        import sys
        _max_int = sys.maxsize
        sums = [0]
        for i in range(n):
            sums.append(sums[i]+nums[i])
        dp = [[_max_int for i in range(m+1)] for j in range(n+1)]
        # dp[0][1] = nums[0]
        dp[0][0] = 0
        # list_display(dp)

        for i in range(1, n+1):
            for j in range(1, min(i, m)+1):
                for k in range(i):
                    mm = max(dp[k][j-1], sums[i]-sums[k])
                    dp[i][j] = min(dp[i][j], mm)
        # list_display(dp)
        ans = dp[n][m]
        return ans


solve = Solution()

questions = [
    ([7, 2, 5, 10, 8], 2),
]

# for qi, q in enumerate(questions):
#     print(f'#{qi}:', q)
#     # print('ans:', solve.splitArray(q[0], q[1]))
#     print('ans:', getattr(solve, 'splitArray')(q[0], q[1]))

work(questions, lambda q: solve.splitArray(q[0], q[1]))



